栈的两种实现方式

小灰灰 2021-04-23 16:20 665阅读 0赞

栈有2种实现方式，分别是数组实现和链表实现。

数组实现的栈称为顺序栈，在内存中是连续存放。顺序栈中存放元素的个数有限，因此入栈的时候要判断是否已满。顺序栈中各种方法的时间复杂度均为O(1)，因此是高效率的数据结构，缺点是对内存利用不够灵活。

链表实现的栈为链式栈，在内存中是分散的。存放节点数目不定。更加合理的利用内存，内存开销更小。

The **array implementation** aims to create an array where the first element (usually at the zero-offset) is the bottom. That is, array\[0\] is the first element pushed onto the stack and the last element popped off. The program must keep track of the size, or the length of the stack. The stack itself can therefore be effectively implemented as a two-element structure in C:

typedef struct \{ int size; int items\[STACKSIZE\]; \} STACK;

The push() operation is used both to initialize the stack, and to store values to it. It is responsible for inserting (copying) the value into the ps->items\[\] array and for incrementing the element counter (ps->size). In a responsible C implementation, it is also necessary to check whether the array is already full to prevent an overrun.

void push(STACK \*ps, int x) \{ if (ps->size == STACKSIZE) \{ fputs("Error: stack overflow\\n", stderr); abort(); \} else ps->items\[ps->size++\] = x; \}

The pop() operation is responsible for removing a value from the stack, and decrementing the value of ps->size. A responsible C implementation will also need to check that the array is not already empty.

int pop(STACK \*ps) \{ if (ps->size == 0)\{ fputs("Error: stack underflow\\n", stderr); abort(); \} else return ps->items\[--ps->size\]; \}

If we use a dynamic array, then we can implement a stack that can grow or shrink as much as needed. The size of the stack is simply the size of the dynamic array. A dynamic array is a very efficient implementation of a stack, since adding items to or removing items from the end of a dynamic array is amortized O(1) time.

\[ edit \] Linked list

The **linked-list** implementation is equally simple and straightforward. In fact, a simple singly linked list is sufficient to implement a stack -- it only requires that the head node or element can be removed, or popped, and a node can only be inserted by becoming the new head node.

Unlike the array implementation, our structure typedef corresponds not to the entire stack structure, but to a single node:

typedef struct stack \{ int data; struct stack \*next; \} STACK;

Such a node is identical to a typical singly linked list node, at least to those that are implemented in C.

The push() operation both initializes an empty stack, and adds a new node to a non-empty one. It works by receiving a data value to push onto the stack, along with a target stack, creating a new node by allocating memory for it, and then inserting it into a linked list as the new head:

void push(STACK \*\*head, int value) \{ STACK \*node = malloc(sizeof(STACK)); /\* create a new node \*/ if (node == NULL)\{ fputs("Error: no space available for node\\n", stderr); abort(); \} else \{ /\* initialize node \*/ node->data = value; node->next = empty(\*head) ? NULL : \*head; /\* insert new head if any \*/ \*head = node; \} \}

A pop() operation removes the head from the linked list, and assigns the pointer to the head to the previous second node. It checks whether the list is empty before popping from it:

int pop(STACK \*\*head) \{ if (empty(\*head)) \{ /\* stack is empty \*/ fputs("Error: stack underflow\\n", stderr); abort(); \} else \{ /\* pop a node \*/ STACK \*top = \*head; int value = top->data; \*head = top->next; free(top); return value; \} \}