This series is my summary of data structure and algorithm when I was looking for a job many years ago. There are basic parts and classic interview questions of various companies. It was first published on CSDN. Is sorted out for a series of friends in need of reference, if there is a mistake, welcome to correct. The full code address for this series is here.
0 overview
As a basic data structure, stack is used in many places, such as function recursion, prefix and suffix expression conversion, etc. This article will use C array to realize the stack structure (use the linked list implementation can see the linked list section, use the header method to build the linked list), and several common stack related interview questions are analyzed, the code of this article is here.
1 definition
We use structs to define stacks and flexible arrays to store elements. Several macros are defined to calculate the number of elements in a stack and whether the stack is empty or full.
typedef struct Stack {
int capacity;
int top;
int items[];
} Stack;
#define SIZE(stack) (stack->top + 1)
#define IS_EMPTY(stack) (stack->top == -1)
#define IS_FULL(stack) (stack->top == stack->capacity - 1)
Copy the code2 Basic Operations
There are three basic operations on the stack:
- Push: Pushes an element onto the stack.
- Pop: Pops the top element of the stack and returns.
- Peek: Fetching the top element of the stack, but not modifying the stack.
As shown in the figure:
The code is as follows:
Stack *stackNew(int capacity)
{
Stack *stack = (Stack *)malloc(sizeof(*stack) + sizeof(int) * capacity);
if(! stack) {printf("Stack new failed\n");
exit(E_NOMEM);
}
stack->capacity = capacity;
stack->top = -1;
return stack;
}
void push(Stack *stack, int v)
{
if (IS_FULL(stack)) {
printf("Stack Overflow\n");
exit(E_FULL);
}
stack->items[++stack->top] = v;
}
int pop(Stack *stack)
{
if (IS_EMPTY(stack)) {
printf("Stack Empty\n");
exit(E_EMPTY);
}
return stack->items[stack->top--];
}
int peek(Stack *stack)
{
if (IS_EMPTY(stack)) {
printf("Stack Empty\n");
exit(E_EMPTY);
}
return stack->items[stack->top];
}
Copy the codeStack related interview questions
3.1 Postfix expression evaluation
Given a suffix expression 6 5 2 3 + 8 * + 3 + *, find the value of the suffix expression.
Solution: Postfix expressions, also known as inverse Polish expressions, can be evaluated using stacks to assist storage. Then its evaluation process is as follows:
- 1) Iterate through the expression, the number encountered is first put into the stack, then the stack is
[6 2, 3, 5]。 - 2) Read on
+, then pop up 3 and 2 to calculate3 + 2And the result is equal to5And will5Push it onto the stack. The stack is zero5 5] [6。 - 3) read
8, put it directly on the stack,[6] 5 5 8。 - 4) read
*That pop up8和5To calculate the8 * 5And will result40Push it onto the stack[40] 6 5. And then the process is similar, read+That will be40和5Pop up,40 + 5The results of the45Push into the stack, and the stack becomes[6] 45, read 3 and put it on the stack45 3 [6]. And so on, and so on288.
Code:
int evaluatePostfix(char *exp)
{
Stack* stack = stackNew(strlen(exp));
int i;
if(! stack) {printf("New stack failed\n");
exit(E_NOMEM);
}
for(i = 0; exp[i]; ++ I) {// If it is a number, press it directlyif (isdigit(exp[i])) {
push(stack, exp[i] - '0');
} elseInt val1 = pop(stack); int val1 = pop(stack); int val2 = pop(stack); switch (exp[i]) {case '+': push(stack, val2 + val1); break;
case The '-': push(stack, val2 - val1); break;
case The '*': push(stack, val2 * val1); break;
case '/': push(stack, val2/val1); break; }}}return pop(stack);
}
Copy the code3.2 stack reverse
Given a stack, reverse it.
Solution 1: If you don’t care about space complexity, you can create another secondary stack, pop all the data from the original stack and push it to the secondary stack.
Solution 2: If you come across this question in an interview, you are expected to do it in a better way. You can first implement a function that inserts elements at the bottom of the stack, and then recursively reverse the stack without using a secondary stack.
*/ void insertAtBottom(Stack * Stack, int v) {if (IS_EMPTY(stack)) {
push(stack, v);
} else{ int x = pop(stack); insertAtBottom(stack, v); push(stack, x); } /** * Stack reverse */ void stackReverse(Stack * Stack) {if (IS_EMPTY(stack))
return;
int top = pop(stack);
stackReverse(stack);
insertAtBottom(stack, top);
}
Copy the code3.3 Design a stack containing min functions
Design a stack such that push, pop, and MIN (fetching the smallest element in the stack) can be completed in constant time.
Analysis: At first, it is easy to think of a method, which is to create an additional minimum binary heap to hold all the elements, so that each time to fetch the smallest element only O(1) time. However, in order to build a minimum heap for push and pop operations, O(LGN) time is required (assuming n elements in the stack).
Solution 1: Auxiliary stack method
So in order to do that, you can use a helper stack and you can use a helper stack to hold the smallest element, which is simple and elegant. Let the secondary stack be named minStack and the top element of the stack be the smallest element in the current stack. This means that
- 1) To get the smallest element in the current stack, just return the top element of the minStack.
- 2) Each time a push operation is performed, check whether the element of push is less than or equal to the element at the top of the minStack. If so, push that element into the minStack as well.
- 3) When performing the POP operation, check whether the pop element is equal to the current minimum value. If it is equal, the element needs to be popped out of the minStack.
Code:
void minStackPush(Stack *orgStack, Stack *minStack, int v)
{
if (IS_FULL(orgStack)) {
printf("Stack Full\n");
exit(E_FULL);
}
push(orgStack, v);
if (IS_EMPTY(minStack) || v < peek(minStack)) {
push(minStack, v);
}
}
int minStackPop(Stack *orgStack, Stack *minStack)
{
if (IS_EMPTY(orgStack)) {
printf("Stack Empty\n");
exit(E_EMPTY);
}
if (peek(orgStack) == peek(minStack)) {
pop(minStack);
}
return pop(orgStack);
}
int minStackMin(Stack *minStack)
{
return peek(minStack);
}
Copy the codeExample:
Suppose we have elements 3,4,2,5,1 pushed into orgStack and elements 3,2,1 in minStack.
Solution 2: Difference method
Another approach uses the memory difference without the need for a secondary stack, which is more subtle:
- The stack has at most one more space for storing the stack minimum.
pushIs the difference between the current element and the smallest element in the stack before it is pressed (the element at the top of the stack), then by comparing the size of the current element with the smallest element in the current stack, and pushing the smaller value of them as the new minimum.popWhen the function executes, firstpopTwo values out of the top of the stack, which are the smallest values in the current stackminAnd the difference between the last pushed element and the minimum value in the previous stackdelta. According to thedelta < 0ordelta >= 0To get the value of the element that was pushed on the stack and the new minimum value of that element after it is pushed off the stack.minThe function just takes the top element of the stack.
Code:
void minStackPushUseDelta(Stack *stack, int v)
{
if(IS_EMPTY(stack)) {// Empty stack, push v twice; push(stack, v); }else {
int oldMin= pop(stack); Int delta = v - oldM; int delta = v - oldMin;
int newMin = delta < 0 ? v : oldMin; push(stack, delta); // The difference between v and the minimum value in the previous stack push(stack, newM)in); }} int minStackPopUseDelta(Stack * Stack) {int min = pop(Stack); int delta = pop(stack); int v, oldMin;
if(delta < 0) {// The last element is smaller than min, then min is the last element v = min; oldMin = v - delta;
} else{// The last value pressed is not the minimum value, then min is oldMin. oldMin = min;
v = oldMin + delta;
}
if(! IS_EMPTY(stack)) {// If the stack is not empty, the oldM is pressedin
push(stack, oldMin);
}
return v;
}
int minStackMinUseDelta(Stack *stack)
{
return peek(stack);
}
Copy the codeExample:
Push (3) : [3] 3 push (4) : 1 3 [3] push (2) : 1-1, 2] [3 push (5) : 1-1 3 2] [3 push (1) : 1-3-1 1 [3] min () : 1, pop () : 1, 3 2] [3 1-1 min () : 2, pop () : 5, 1-1, 2] [3 min () : 2, pop () : 2, 3] [3 1 min () : 3, pop () : 4, [3] 3 min () : 3, pop () : 3. []Copy the code3.4 Find out the number of stacks and the sequence of out stacks
Find the number of stacks
Given a stack sequence, try to find all possible stack sequences. For example, if the stack sequence is 1, 2, 3, there are five possible stack sequences: 1, 2, 3, 1, 3, 2, 3, 1, 2, 1.
Solution: ask to solve the stack sequence number, still calculate relatively easy. Many articles have analyzed this problem, and the final answer is the Cattelan number, which means that the total number of stack sequences of n elements is equal to C(2n, n) – C(2n, n-1) = C(2n, n)/(n+1), For example, the total stack number of 3 elements is C(6, 3) / 4 = 5.
If you don’t analyze the general term formula, can you write a program to find the number of sequences out of the stack? The answer is yes, according to the current state of the stack, we can add the total number of the two cases of pushing an element and pushing an element to get the total number of the stack.
/** * count stacks * -in: Number of elements in the stack * -out: number of elements out of the stack * -wait*/ int sumOfStackPopSequence(Stack * Stack, intin, int out, int wait)
{
if(out == stack->capacity) {// All elements out of the stack, return 1return 1;
}
int sum = 0;
if (wait> 0) sum += sumOfStackPopSequence(stack,in + 1, out, wait - 1);
if (in> 0) sum += sumOfStackPopSequence(stack,in - 1, out + 1, wait);
return sum;
}
Copy the codeFind all out stack sequences
Given an input sequence input[] = {1, 2, 3}, print all possible stack sequences.
Solution: This is a bit difficult, not only the stack number, need to print all the stack sequence, need to use backtracking method, backtracking method is much more difficult than simple recursion, later there is time to separate a backtracking method article. For each input, there are two situations: whether the elements in the original stack are removed from the stack first or removed from the stack first. Here, two stacks are used to achieve this, where the stack STK is used to simulate the entry and exit of the stack, and the stack output is used to store the value of the exit stack. Note that the exit condition is that when all input elements are traversed, there may be elements in both stack STK and output. It is necessary to print the stack OUTPUT from the bottom of the stack first, and then print the stack STK from the top of the stack. Another point is that the branch ends when the simulation stack we are using, STK, is empty. The code is as follows:
void printStackPopSequence(int input[], int i, int n, Stack *stk, Stack *output)
{
if(i >= n) { stackTraverseBottom(output); // output prints stackTraverseTop(STK) from the bottom of the stack; // STK prints from the top of the stackprintf("\n");
return;
}
push(stk, input[i]);
printStackPopSequence(input, i+1, n, stk, output);
pop(stk);
if (IS_EMPTY(stk))
return;
int v = pop(stk);
push(output, v);
printStackPopSequence(input, i, n, stk, output);
push(stk, v);
pop(output);
}
Copy the codeThe resources
- www.techiedelight.com/stack-imple…
- www.geeksforgeeks.org/stack-set-4…
- www.geeksforgeeks.org/reverse-a-s…
- Blog.csdn.net/yysdsyl/art…