栈中使用两个指针链表，分别为栈顺序链表和大小顺序链表。
/**
Description:
We all know the famous link list. We can use these to hold data in a linear fashion. The link list can be used to implement a stack as well for example.
For this challenge you will need to develop a smart stack list. So what makes this link list so smart? This link list will behave like a stack but also maintain an ascending sorted order of the data as well. So our link list maintains 2 orders (stack and sorted)
In today's world link list data structures are part of many development platforms. For this challenge you will be implementing this and not using already pre-made frameworks/standard link lists code that you call. You have to implement it and all the features.
The Challenge will have 2 steps.
Implement your smart link list
Test your smart link list
Data:
The smart link list will hold integer data.
Methods:
The smart link list must support these methods or operations.
Push - Push a number on top of the stack (our link list is a stack)
Pop - Pop the number off the top of the stack
Size - how many numbers are on your stack
Remove Greater - remove all integers off the stack greater in value then the given number
Display Stack - shows the stack order of the list (the order they were pushed from recent to oldest)
Display Ordered - shows the integers sorted from lowest to highest.
Smart list:
One could make a stack and when you do the display ordered do a sort. But our smart list must have a way so that it takes O(n) to display the link list in stack order or ascending order. In other words our link list is always in stack and sorted order. How do you make this work? That is the real challenge.
Test your list:
Develop a quick program that uses your smart stack list.
Generate a random number between 1-40. Call this number n.
Generate n random numbers between -1000 to 1000 and push them on your list
Display stack and sorted order
Generate a random number between -1000 and 1000 can call it x
Remove greater X from your list. (all integers greater than x)
Display stack and sorted order
pop your list (size of list / 2) times (50% of your list is removed)
Display stack and sorted order
**/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
typedef struct Node{
void *owner;
Node *pre;
Node *next;
}Node;
typedef struct NodeList{
Node *head;
Node *tail;
};
void Insert(Node *p, Node *q){
if (!p || !q){
return;
}
p->next = q;
p->pre = q->pre;
if (q->pre){
q->pre->next = p;
}
q->pre = p;
}
void Remove(Node *p){
if (!p){
return;
}
if (p->next){
p->next->pre = p->pre;
}
if (p->pre){
p->pre->next = p->next;
}
p->pre = NULL;
p->next = NULL;
}
typedef struct StackNode{
Node stackNode;
Node orderNode;
int val;
};
typedef struct Stack{
NodeList orderList;
NodeList stackList;
int size;
};
int GetVal(Node *p){
return ((StackNode *)(p->owner))->val;
}
void InsertByOrder(Node *p, Stack *stack){
Node *q = stack->orderList.head;
int val = GetVal(p);
//处理空情况
if (!q){
stack->orderList.head = p;
stack->orderList.tail = p;
return;
}
while (q){
int k = GetVal(q);
if (val <= k){
Insert(p, q);
//处理最小情况
if (stack->orderList.head == q){
stack->orderList.head = p;
}
return;
}
else{
q = q->next;
}
}
//处理最大情况
p->pre = stack->orderList.tail;
stack->orderList.tail->next = p;
stack->orderList.tail = p;
}
void Push(int val, Stack *stack){
StackNode *p = (StackNode *)malloc(sizeof(StackNode));
if (!p){
exit(EXIT_FAILURE);
}
p->orderNode.pre = NULL;
p->orderNode.next = NULL;
p->orderNode.owner = p;
p->stackNode.pre = NULL;
p->stackNode.next = NULL;
p->stackNode.owner = p;
p->val = val;
//空的stack
if (stack->orderList.head == NULL){
stack->orderList.head = &(p->orderNode);
stack->orderList.tail = stack->orderList.head;
stack->stackList.head = &(p->stackNode);
stack->stackList.tail = stack->stackList.head;
stack->size = 1;
return;
}
//将p的stack节点插入合适位置
Insert(&(p->stackNode), stack->stackList.head);
stack->stackList.head = &(p->stackNode);
//将p的order节点插入合适位置
InsertByOrder(&(p->orderNode), stack);
++stack->size;
}
void Pop(Stack *stack){
//stack 不可以为空
assert(stack->orderList.head);
--stack->size;
//最后一个节点的情况
if (stack->orderList.head == stack->orderList.tail){
StackNode *p = (StackNode *)(stack->orderList.head->owner);
free(p);
stack->orderList.head = NULL;
stack->orderList.tail = NULL;
stack->stackList.head = NULL;
stack->stackList.tail = NULL;
return;
}
StackNode *p = (StackNode *)(stack->stackList.head);
//更新orderlist
if ((StackNode *)(stack->orderList.head->owner) == p){
stack->orderList.head = p->orderNode.next;
}
//更新stackList
stack->stackList.head = p->stackNode.next;
Remove(&(p->orderNode));
Remove(&(p->stackNode));
free(p);
}
int Size(Stack* stack){
return stack->size;
}
void RemoveGreater(int num, Stack *stack){
StackNode *p = (StackNode *)(stack->orderList.head->owner);
while (p){
int val = GetVal(&(p->orderNode));
if (val > num){
break;
}
else{
if (p->orderNode.next){
p = (StackNode *)(p->orderNode.next->owner);
}
else{
p = NULL;
}
}
}
while (p){
if ((StackNode *)(stack->orderList.head->owner) == p){
stack->orderList.head = p->orderNode.next;
}
if ((StackNode *)(stack->orderList.tail->owner) == p){
stack->orderList.tail = p->orderNode.pre;
}
if ((StackNode *)(stack->stackList.head->owner) == p){
stack->stackList.head = p->stackNode.next;
}
if ((StackNode *)(stack->stackList.tail->owner) == p){
stack->stackList.tail = p->stackNode.pre;
}
StackNode *q = NULL;
if (p->orderNode.next){
q = (StackNode *)(p->orderNode.next->owner);
}
Remove(&(p->orderNode));
Remove(&(p->stackNode));
free(p);
p = q;
--stack->size;
assert(stack->size >= 0);
}
}
void DisplayByStack(Stack *stack){
if (stack->orderList.head == NULL){
printf("empty stack\n");
return;
}
StackNode *p = (StackNode *)(stack->stackList.head->owner);
printf("display by stack:\n");
while (p){
printf("%d ", p->val);
if (p->stackNode.next){
p = (StackNode *)(p->stackNode.next->owner);
}
else{
p = NULL;
}
}
printf("\n");
}
void DisplayByOrder(Stack *stack){
if (stack->orderList.head == NULL){
printf("empty stack\n");
return;
}
StackNode *p = (StackNode *)(stack->orderList.head->owner);
printf("display by order:\n");
while (p){
printf("%d ", p->val);
if (p->orderNode.next){
p = (StackNode *)(p->orderNode.next->owner);
}
else{
p = NULL;
}
}
printf("\n");
}
//Generate a random number between 1 - 40. Call this number n.
//Generate n random numbers between - 1000 to 1000 and push them on your list
//Display stack and sorted order
//Generate a random number between - 1000 and 1000 can call it x
//Remove greater X from your list. (all integers greater than x)
//Display stack and sorted order
//pop your list(size of list / 2) times(50 % of your list is removed)
//Display stack and sorted order
int GenerateRandom(int low, int hight){
double k = (double)rand();
while (k > 1){
k = k / 10;
}
return (k * (hight - low)) + low;
}
int main(){
srand((unsigned)time(NULL));
for (int i = 1000; i >= 0; --i){
Stack stack;
stack.orderList.head = NULL;
stack.orderList.tail = NULL;
stack.stackList.head = NULL;
stack.stackList.tail = NULL;
stack.size = 0;
int n = GenerateRandom(1, 40);
for (int i = 0; i < n; ++i){
int k = GenerateRandom(-1000, 1000);
printf("push number :%d\n", k);
Push(k, &stack);
}
DisplayByStack(&stack);
DisplayByOrder(&stack);
printf("\n");
int x = GenerateRandom(-1000, 1000);
printf("remove greater than :%d\n", x);
RemoveGreater(x, &stack);
DisplayByStack(&stack);
DisplayByOrder(&stack);
printf("\n");
int m = Size(&stack);
for (int i = 0; i < m / 2; ++i){
Pop(&stack);
}
printf("pop half of stack size\n");
DisplayByStack(&stack);
DisplayByOrder(&stack);
}
return 0;
}
