Question

用链表和数组两种方式分别实现栈的出栈、入栈、取栈顶元素、判空、查找等操作。

Answer 1

/* linkedlist.h */
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

typedef struct node *link;
struct node {
unsigned char item;
link next;
};

link make_node(unsigned char item);
void free_node(link p);
link search(unsigned char key);
void insert(link p);
void delete(link p);
void traverse(void (*visit)(link));
void destroy(void);
void push(link p);
link pop(void);

#endif

/* linkedlist.c */
#include <stdlib.h>
#include "linkedlist.h"

static link head = NULL;

link make_node(unsigned char item)
{
link p = malloc(sizeof *p);
p->item = item;
p->next = NULL;
return p;
}

void free_node(link p)
{
free(p);
}

link search(unsigned char key)
{
link p;
for (p = head; p; p = p->next)
if (p->item == key)
return p;
return NULL;
}

void insert(link p)
{
p->next = head;
head = p;
}

void delete(link p)
{
link pre;
if (p == head) {
head = p->next;
return;
}
for (pre = head; pre; pre = pre->next)
if (pre->next == p) {
pre->next = p->next;
return;
}
}

void traverse(void (*visit)(link))
{
link p;
for (p = head; p; p = p->next)
visit(p);
}

void destroy(void)
{
link q, p = head;
head = NULL;
while (p) {
q = p;
p = p->next;
free_node(q);
}
}

void push(link p)
{
insert(p);
}

link pop(void)
{
if (head == NULL)
return NULL;
else {
link p = head;
head = head->next;
return p;
}
}
/* main.c */
#include <stdio.h>
#include "linkedlist.h"

void print_item(link p)
{
printf("%d\n", p->item);
}

int main(void)
{
link p = make_node(10);
insert(p);
p = make_node(5);
insert(p);
p = make_node(90);
insert(p);
p = search(5);
delete(p);
free_node(p);
traverse(print_item);
destroy();

p = make_node(100);
push(p);
p = make_node(200);
push(p);
p = make_node(250);
push(p);
while (p = pop()) {
print_item(p);
free_node(p);
}

return 0;
}
上面是用键表实现的堆栈，下面是用数组实现的堆栈
#include <stdio.h>

char stack[512];
int top = 0;

void push(char c)
{
stack[top++] = c;
}

char pop(void)
{
return stack[--top];
}

int is_empty(void)
{
return top == 0;
}

int main(void)
{
push('a');
push('b');
push('c');

while(!is_empty())
putchar(pop());
putchar('\n');

return 0;
}

Answer 2

#include <iostream>
using namespace std;

class MyStack{
public:
MyStack();
void push(char next);
char &ttop();
void pop();
bool is_Empty();
int cmp(char item);
private:
int top;
char stack[100];
};

int main(void){
MyStack myStack;
int i, j;
char expression[20] = "1*(2+3*5)-2*3+4*8";
char nibolan[20] = {'\0'};
char m;
cout << expression << endl;
i = 0;
j = -1;
m = '\0';
myStack.push(m);
while(expression[i] != '\0')
{
char item = expression[i];

if(item >= '0' && item <= '9')
nibolan[++j] = item;
else if(item == '(')
myStack.push(item);
else if(item == ')')
{
while(myStack.ttop() != '(')
{
nibolan[++j] = myStack.ttop();
myStack.pop();
}
myStack.pop();
}
else if(myStack.cmp(myStack.ttop()) == 0)
myStack.push(item);
else
{
while(myStack.cmp(myStack.ttop()) != 0 && myStack.cmp(item) <= myStack.cmp(myStack.ttop()))
{
nibolan[++j] = myStack.ttop();
myStack.pop();
}
myStack.push(item);
}
i++;
}
while(!myStack.is_Empty())
{
nibolan[++j] = myStack.ttop();
myStack.pop();
}

cout << nibolan << endl;
}

MyStack::MyStack(){ top = -1; }
void MyStack::push(char next){ stack[++top] = next; }
bool MyStack::is_Empty(){
if(top == -1)
return true;
else
return false;
}
char &MyStack::ttop(){ return stack[top]; }
void MyStack::pop(){ top--; }
int MyStack::cmp(char item){
switch(item){
case '+': case '-':
return 1;
break;
case '*': case '/':
return 2;
break;
default:
return 0;
break;
}
}