函数题：Linked List Implementation of Stacks

A stack is a list with the restriction that inserts and deletes can be performed in only one position, namely the end of ofthe list called the top. The fundamental operations on a stack are push, which is equivalent to an insert, and pop, whichdeletes the most recently inserted element. The most recently inserted element can be examined prior to performing a pop by use of the top routine. A pop or top on an empty stack is generally considered an error in the stack ADT. On the other hand, running out of space when performing a push is an implementation error but not an ADT error.

Stacks are sometimes known as LIFO (last in, first out) lists. The model depicted in Figure 3.37 signifies only thatpushes are input operations and pops and tops are output. The usual operations to make empty stacks and test foremptiness are part of the repertoire, but essentially all that you can do to a stack is push and pop. Figure 3.38 shows an abstract stack after several operations. The general model is that there is some element that is atthe top of the stack, and it is the only element that is visible.


Of course, since a stack is a list, any list implementation will do. We will give two popular implementations. One usespointers and the other uses an array, but, as we saw in the previous section, if we use good rogramming principles the calling routines do not need to know which method is being used.

The first implementation of a stack uses a singly linked list. We perform a push by inserting at the front of the list. Weperform a pop by deleting the element at the front of the list. A top operation merely examines the element at the frontof the list, returning its value. Sometimes the pop and top operations are combined into one. We could use calls to thelinked list routines of the previous section, but we will rewrite the stack routines from scratch for the sake of clarity.

First, we give the definitions in Figure 3.39. We implement the stack using a header. Then Figure 3.40 shows that anempty stack is tested for in the same manner as an empty list.

Creating an empty stack is also simple. We merely create a header node; make_null sets the next pointer to NULL (seeFig. 3.41). The push is implemented as an insertion into the front of a linked list, where the front of the list serves asthe top of the stack (see Fig. 3.42). The top is performed by examining the element in the first position of the list (seeFig. 3.43). Finally, we implement pop as a delete from the front of the list (see Fig. 3.44).

### 函数接口定义：
c++
typedef int ElementType;

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;

//Test whether a stack is empty
int IsEmpty(Stack S);

//Create an empty stack
Stack CreateStack(void);

//Free a stack
void DisposeStack(Stack S);

//Make a stack empty
void MakeEmpty(Stack S);

//Push onto a stack
void Push(ElementType X, Stack S);

//Return top element in a stack
ElementType Top(Stack S);

//Pop from a stack
void Pop(Stack S);

struct Node
{
ElementType Element;
PtrToNode Next;
};



### 裁判测试程序样例：
在这里给出函数被调用进行测试的例子。
c++
int main(void)
{//从键盘输入正整数序列，以 0 结束输入。逆序输出。
Stack S = CreateStack();
int x;
scanf("%d", &x);
while (x != 0)
{
Push(x, S);
scanf("%d", &x);
}
while (!IsEmpty(S))
{
x = Top(S);
printf("%d ", x);
Pop(S);
}
DisposeStack(S);
return 0;
}

/* 请在这里填写答案 */


### 输入样例：

在这里给出一组输入。例如：

in
1 2 3 4 5 6 0


### 输出样例：

在这里给出相应的输出。例如：

out
6 5 4 3 2 1







答案：若无答案欢迎评论