This is the 15th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Chapter 3 Stacks and Queues

The stack

3.1.1 Definition and Features of the stack

  1. Defines a linear table that can only be inserted or deleted at one end of the table (the top of the stack)
  2. The logical structure is the same as the linear table, which is still a one-to-one relationship
  3. The storage structure can be sequential stack or chain stack, but the sequential stack is more common
  4. Operations can only be performed at the top of the stack, and nodes are accessed on a last in, first out (LIFO) or first in, first out (FILO) basis
  5. The main operation of the stack and out of the stack function, specific implementation according to the order of the stack or chain stack of different and different basic operations have the stack, out of the stack, read the top element value of the stack, build the stack, judge the stack full, empty stack, etc

3.1.2 Stack representation and operation implementation

“In” =PUSH =PUSH () “Out” =POP =POP ()

Representation of the sequential stack

  • Top indicates what to do when the stack is full of the subscript address above the actual top element:

1, error, return to operating system. 2. Allocate more space as the storage space of the stack, and move the contents of the original stack to the new stack.

// The first storage structure: the sequential stack representation
#define  MAXSIZE  100
typedef  struct
{
SElemType  *base; SElemType  *top; 
int stacksize;
}SqStack;
Copy the code
Operation 1: Sequential stack initialization (construct an empty stack)

[Algorithm steps] (1) Allocate space and check whether the space allocation failed, if failed, return error (2) set the bottom and top of the stack pointer S.stack = S.stack; (3) Set the stack size

// [algorithm description] Sequence stack initialization

Status InitStack (SqStack &S) {s.case =newSElemType [MAXSIZE];if(! S.b ase)return OVERFLOW; S.top = S.base;
S.stackSize = MAXSIZE;
return OK;
}
Copy the code
Operation 2: Check whether the sequential stack is empty

[Algorithm Step] Determine whether the top and bottom Pointers are equal. [Algorithm Description] Determine whether the order stack is empty

Bool StackEmpty (SqStack S) {if (s.stack == s.stack) return true; else return false; }Copy the code
Operation 3: Find the length of the sequential stack

[Algorithm description] Find the length of the order stack

Int StackLength (SqStack S) {return s.stack -- s.stack; }Copy the code
Operation 4: Clear the sequential stack

Let the top of the stack and the bottom of the stack have the same point, are pointing to the bottom of the stack

Status ClearStack (SqStack S) {if (s.stack) s.stack = s.stack; return OK; }Copy the code
Operation 5: Destroy the sequential stack

(1) release all memory space (2) set the three member variables of the sequential stack to zero to destroy the sequential stack

Status DestroyStack (SqStack &S) {if (s.stack) {delete s.stack; S.stacksize = 0; S.base = S.top = NULL; } return OK; }Copy the code
Operation 6: Sequential stack pushing

(1) Determine whether the stack is full, if it is full, the error is made. (2) the element e pushes the top of the stack. (3) The pointer to the top of the stack increases by 1

Status Push (SqStack &S, SElemType e) {if (s.stack - s.sheet == s.tacksize) return ERROR; *S.top++=e; return OK; }Copy the code
Operation 7: Stack out in sequence

(1) determine whether the stack is empty, if empty, error (2) get the top of the stack element E (3) the top of the stack pointer minus 1

Status Pop (SqStack &S, SElemType &e) {if (s.stack == s.stack) return ERROR; E = * - S.t op; return OK; }Copy the code
Operation 8: Take the top element of the sequential stack

(1) Determine whether the stack is empty, if empty, return error (2) otherwise through the top of the stack pointer to get the top of the stack element

Status GetTop (SqStack S, SElemType &e) {if (s.stack == s.case) return ERROR; // stack empty e = * (s.op -- 1); return OK; }Copy the code

The stack and recursion

  • Definition of recursion An object is said to be recursive if it partly contains itself or is defined by itself. A procedure is said to be recursive if it calls itself directly or indirectly.
  • Methods for solving recursive problems
  • Divide and conquer: a more complex problem can be decomposed into several relatively simple subproblems with the same or similar solutions to solve the necessary three conditions
  • (1) Can transform a problem into a new problem, and the solution of the new problem and the original problem is the same or similar, the only difference is the object, and these processing objects are changing regularly
  • (2) The above-mentioned transformation can simplify the problem
  • (3) There must be a clear exit to recursion, or the boundary of recursion

Definition and characteristics of stacks and queues

  1. Defines a linear table that can only be inserted at one end of the table and deleted at the other end
  2. The logical structure is the same as the linear table, which is still a one-to-one relationship
  3. The storage structure can be stored in either sequential queue or chain queue

4. Operation rules first in first out (FIFO) 5. Main operation in and out of the queue function, specific implementation according to the order of the queue or chain queue of different stacks, queue and the general difference between the linear table stack, queue is a special (operation limited) of the linear table

Difference: only the operation rules are different

  • General linear table

Logical structure: one to one storage structure: sequential list, linked list operation rules: random, sequential access

  • The queue

Logical structure: one-to-one storage structure: sequential queue, chain queue Operation rule: first-in, first-out

  • The stack

Logical structure: one to one storage structure: sequential stack, chain stack operation rule: last in first out